/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/coins-in-a-line-ii
@Language: C++
@Datetime: 16-02-09 05:44
*/

class Solution {
public:
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int N=values.size();
        if (N<3) return true;
        
        vector<int> first(N,0);
        vector<int> second(N,0);
        first[N-1]=values[N-1];
        first[N-2]=values[N-1]+values[N-2];
        
        for(int i=N-3;i>=0;--i){
            if (second[i+1]+values[i]>second[i+2]+values[i]+values[i+1]){
                first[i]=second[i+1]+values[i];
                second[i]=first[i+1];
            }
            else{
                first[i]=second[i+2]+values[i]+values[i+1];
                second[i]=first[i+2];
            }
        }
        return first[0]>second[0];
    }
};